lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/dp/lcs.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#define}}\ \textbf{\textcolor{Black}{MAX}}\textcolor{BrickRed}{(}a\textcolor{BrickRed}{,}b\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{((}a\textcolor{BrickRed}{$>$}b\textcolor{BrickRed}{)?(}a\textcolor{BrickRed}{):(}b\textcolor{BrickRed}{))} \\
   6 \mbox{}\textcolor{ForestGreen}{int}\ dp\textcolor{BrickRed}{[}\textcolor{Purple}{1001}\textcolor{BrickRed}{][}\textcolor{Purple}{1001}\textcolor{BrickRed}{];} \\
   7 \mbox{} \\
   8 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{lcs}}\textcolor{BrickRed}{(}\textbf{\textcolor{Blue}{const}}\ string\ \textcolor{BrickRed}{\&}s\textcolor{BrickRed}{,}\ \textbf{\textcolor{Blue}{const}}\ string\ \textcolor{BrickRed}{\&}t\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
   9 \mbox{}\ \ \textcolor{ForestGreen}{int}\ m\ \textcolor{BrickRed}{=}\ s\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{(),}\ n\ \textcolor{BrickRed}{=}\ t\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();} \\
  10 \mbox{}\ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}m\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0}\ \textcolor{BrickRed}{$|$$|$}\ n\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  11 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$=}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)} \\
  12 \mbox{}\ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}\textcolor{Purple}{0}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  13 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$=}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)} \\
  14 \mbox{}\ \ \ \ dp\textcolor{BrickRed}{[}\textcolor{Purple}{0}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  15 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)} \\
  16 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)} \\
  17 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}s\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{==}\ t\textcolor{BrickRed}{[}j\textcolor{BrickRed}{])} \\
  18 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{]+}\textcolor{Purple}{1}\textcolor{BrickRed}{;} \\
  19 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{else}} \\
  20 \mbox{}\ \ \ \ \ \ \ \ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Black}{MAX}}\textcolor{BrickRed}{(}dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{][}j\textcolor{BrickRed}{],}\ dp\textcolor{BrickRed}{[}i\textcolor{BrickRed}{][}j\textcolor{BrickRed}{+}\textcolor{Purple}{1}\textcolor{BrickRed}{]);} \\
  21 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ dp\textcolor{BrickRed}{[}m\textcolor{BrickRed}{][}n\textcolor{BrickRed}{];} \\
  22 \mbox{}\textcolor{Red}{\}} \\
  23
  24 } \normalfont\normalsize